"""
3418. 机器人可以获得的最大金币数
中等
相关标签
相关企业
提示
给你一个 m x n 的网格。一个机器人从网格的左上角 (0, 0) 出发，目标是到达网格的右下角 (m - 1, n - 1)。在任意时刻，机器人只能向右或向下移动。

网格中的每个单元格包含一个值 coins[i][j]：

如果 coins[i][j] >= 0，机器人可以获得该单元格的金币。
如果 coins[i][j] < 0，机器人会遇到一个强盗，强盗会抢走该单元格数值的 绝对值 的金币。
机器人有一项特殊能力，可以在行程中 最多感化 2个单元格的强盗，从而防止这些单元格的金币被抢走。

注意：机器人的总金币数可以是负数。

返回机器人在路径上可以获得的 最大金币数 。



示例 1：

输入： coins = [[0,1,-1],[1,-2,3],[2,-3,4]]

输出： 8

解释：

一个获得最多金币的最优路径如下：

从 (0, 0) 出发，初始金币为 0（总金币 = 0）。
移动到 (0, 1)，获得 1 枚金币（总金币 = 0 + 1 = 1）。
移动到 (1, 1)，遇到强盗抢走 2 枚金币。机器人在此处使用一次感化能力，避免被抢（总金币 = 1）。
移动到 (1, 2)，获得 3 枚金币（总金币 = 1 + 3 = 4）。
移动到 (2, 2)，获得 4 枚金币（总金币 = 4 + 4 = 8）。
示例 2：

输入： coins = [[10,10,10],[10,10,10]]

输出： 40

解释：

一个获得最多金币的最优路径如下：

从 (0, 0) 出发，初始金币为 10（总金币 = 10）。
移动到 (0, 1)，获得 10 枚金币（总金币 = 10 + 10 = 20）。
移动到 (0, 2)，再获得 10 枚金币（总金币 = 20 + 10 = 30）。
移动到 (1, 2)，获得 10 枚金币（总金币 = 30 + 10 = 40）。


提示：

m == coins.length
n == coins[i].length
1 <= m, n <= 500
-1000 <= coins[i][j] <= 1000
"""


class Solution(object):
    def maximumAmount(self, coins):
        """
        :type coins: List[List[int]]
        :rtype: int
        """
        #思路:定义三种状态，分别是已使用0次，1次，2次感化次数
        #当前数字为正数，每种次数取上和左的最大值加上当前即可
        #f[x][y][z],其中x，y代表坐标，z代表感化使用的次数，0代表未使用，1代表使用1次，2代表使用2次
        #当前数字为负数:
        #f[i][j][0] = max(f[i - 1][j][0], f[i][j - 1][0]) + coins[i][j]
        #f[i][j][1] = max(f[i][j - 1][0], f[i - 1][j][0]) #从上方或者左边的次数为0
        #              max(f[i][j - 1][1], f[i - 1][j][1]) + coins[i][j] #从上方或者左边的次数为1,次数不变需要被抢去coins[i][j]
        #f[i][j][2] = max(f[i][j - 1][1], f[i - 1][j][1]) #从上方或者左边的次数为1
        #              max(f[i][j - 1][2], f[i - 1][j][2]) + coins[i][j] #从上方或者左边的次数为2,次数不变需要被抢去coins[i][j]

        # dp[i][j][0] = max(dp[i][j - 1][0], dp[i - 1][j][0]) + coins[i][j]
        # dp[i][j][1] = max(max(dp[i][j - 1][0], dp[i - 1][j][0]),
        #                   max(dp[i][j - 1][1], dp[i - 1][j][1]) - abs(coins[i][j]))
        # dp[i][j][2] = max(max(dp[i][j - 1][1], dp[i - 1][j][1]),
        #                   max(dp[i][j - 1][2], dp[i - 1][j][2]) - abs(coins[i][j]))

        m, n = len(coins),len(coins[0])
        #创建dp，d[i][j][k]表示从(i,j)到(m-1,n-1)的最优解，其中k表示还剩k次感化次数
        dp = [[[0 for _ in range(3)] for _ in range(n)] for _ in range(m)] # to_think 创建三维数组,最里面的是个长度为3的数组
        if coins[0][0] >= 0:
            dp[0][0][0] = coins[0][0]
        else:
            dp[0][0][0] = coins[0][0] #不使用感化则是负数
            dp[0][0][1] = 0
        for i in range(1,m):
            if coins[i][0] >= 0:
                dp[i][0][0] = dp[i-1][0][0] + coins[i][0]
                dp[i][0][1] = dp[i-1][0][1] + coins[i][0]
                dp[i][0][2] = dp[i-1][0][2] + coins[i][0]
            else:
                dp[i][0][0] = dp[i-1][0][0] + coins[i][0] #减去
                dp[i][0][1] = max(dp[i-1][0][1] - abs(coins[i][0]),dp[i-1][0][0] )
                dp[i][0][2] = max(dp[i-1][0][2] - abs(coins[i][0]),dp[i-1][0][1] )
        for  j in range(1,n):
            if coins[0][j] >= 0:
                dp[0][j][0] = dp[0][j-1][0] + coins[0][j]
                dp[0][j][1] = dp[0][j-1][1] + coins[0][j]
                dp[0][j][2] = dp[0][j-1][2] + coins[0][j]
            else:
                dp[0][j][0] = dp[0][j-1][0] + coins[0][j]
                #dp[0][j][1] - abs(coins[0][j] 不感化当前， 和感化当前
                dp[0][j][1] = max(dp[0][j-1][1] - abs(coins[0][j]),dp[0][j-1][0] )
                dp[0][j][2] = max(dp[0][j-1][2] - abs(coins[0][j]),dp[0][j-1][1] )
        for  i in range(1,m):
            for j in range(1,n):
                if coins[i][j] >= 0:
                    dp[i][j][0] = max(dp[i][j-1][0],dp[i-1][j][0]) + coins[i][j]
                    dp[i][j][1] = max(dp[i][j-1][1],dp[i-1][j][1]) + coins[i][j]
                    dp[i][j][2] = max(dp[i][j-1][2],dp[i-1][j][2]) + coins[i][j]
                else:
                    dp[i][j][0] = max(dp[i][j-1][0],dp[i-1][j][0]) + coins[i][j]
                    dp[i][j][1] = max(max(dp[i][j-1][0],dp[i-1][j][0]) ,max(dp[i][j-1][1],dp[i-1][j][1]) - abs(coins[i][j]))
                    dp[i][j][2] = max(max(dp[i][j-1][1],dp[i-1][j][1]) ,max(dp[i][j-1][2],dp[i-1][j][2]) - abs(coins[i][j]))
        return max(dp[m-1][n-1][0],dp[m-1][n-1][1],dp[m-1][n-1][2])

if __name__ == '__main__':
    # print(Solution().maximumAmount([[0,1,-1],[1,-2,3],[2,-3,4]]))
    # print(Solution().maximumAmount([[10,10,10],[10,10,10]]))
    #[[-7,12,12,13],[-6,19,19,-6],[9,-2,-10,16],[-4,14,-10,-9]]
    # print(Solution().maximumAmount([[-7,12,12,13],[-6,19,19,-6],[9,-2,-10,16],[-4,14,-10,-9]])) #60
    #[[-18,-12,-13,-11,17],[11,-7,-9,5,-8],[-3,5,-16,-18,9],[-7,-17,-5,3,-5],[12,-3,4,15,-7]]
    print(Solution().maximumAmount([[-18,-12,-13,-11,17],[11,-7,-9,5,-8],[-3,5,-16,-18,9],[-7,-17,-5,3,-5],[12,-3,4,15,-7]])) #29